/**
 * @file BinaryTree.h
 * @brief
 * @author htli (22235058@zju.edu.cn)
 * @version 1.0
 * @date 2022-11-04
 *
 * @copyright Copyright (c) 2022  linhuo2020
 *
 */
#include <iostream>
using namespace std;
/**
 * @brief Base class for trees.
 * @tparam Comparable
 */
template <typename Comparable>
class BinaryTree
{
public:
    /**
     * Construct a new Binary Tree object
     */
    BinaryTree() : root{nullptr} {}
    /**
     * Destructor for the tree
     */
    virtual ~BinaryTree();
    /**
     * Print the tree contents.
     */
    void printTree(ostream &out = cout) const;
    /**
     * Make the tree logically empty.
     */
    void makeEmpty();
    /**
     * Insert x into the tree; duplicates are ignored.
     */
    virtual void insert(const Comparable &x);
    virtual void insert(Comparable &&x);
    /**
     * Remove x from the tree. Nothing is done if x is not found.
     */
    virtual void remove(const Comparable &x);
    virtual void remove(Comparable &&x);

protected:
    /**
     * @brief Basis struct for all nodes.
     */
    struct Node
    {
        Comparable element;
        Node *left;
        Node *right;
        Node(const Comparable &theElement, Node *lt, Node *rt);
        Node(Comparable &&theElement, Node *lt, Node *rt);
    };

private:
    Node *root = nullptr;
};

/**
 * @brief A binary search tree.
 * @tparam Comparable
 */
template <typename Comparable>
class BstTree : public BinaryTree<Comparable>
{
protected:
    /**
     * @brief Node for binary search tree.
     */
    struct BstNode : BinaryTree<Comparable>::Node
    {
        BstNode(const Comparable &theElement, BstNode *lt, BstNode *rt);
        BstNode(Comparable &&theElement, BstNode *lt, BstNode *rt);
    };

private:
    BstNode *root = nullptr;

public:
    virtual ~BstTree();
    /**
     * Insert x into the tree; duplicates are ignored.
     */
    virtual void insert(const Comparable &x);
    virtual void insert(Comparable &&x);
    /**
     * Remove x from the tree. Nothing is done if x is not found.
     */
    virtual void remove(const Comparable &x);
    virtual void remove(Comparable &&x);
    /**
     * Find the smallest item in the tree.
     */
    const Comparable &findMin() const;
    /**
     * Find the largest item in the tree.
     * Throw UnderflowException if empty.
     */
    const Comparable &findMax() const;
};

/**
 * @brief An Avltree.
 * @tparam Comparable
 */
template <typename Comparable>
class AvlTree : public BstTree<Comparable>
{
protected:
    /**
     * @brief Node with height.
     */
    struct AvlNode : BstTree<Comparable>::BstNode
    {
        int height;
        AvlNode(const Comparable &ele, AvlNode *lt, AvlNode *rt, int h = 0);
        AvlNode(Comparable &&ele, AvlNode *lt, AvlNode *rt, int h = 0);
    };

private:
    AvlNode *root = nullptr;

public:
    virtual ~AvlTree();
    /**
     * Insert x into the tree; duplicates are ignored.
     */
    virtual void insert(const Comparable &x);
    virtual void insert(Comparable &&x);
    /**
     * Remove x from the tree. Nothing is done if x is not found.
     */
    virtual void remove(const Comparable &x);
    virtual void remove(Comparable &&x);

private:
    static const int ALLOWED_IMBALANCE = 1;
    // Assume t is balanced or within one of being balanced
    void balance(AvlNode *&t);
    /**
     * Rotate binary tree node with left child.
     * For AVL trees, this is a single rotation for case 1.
     * Update heights, then set new root.
     */
    void rotateWithLeftChild(AvlNode *&k2);
    /**
     * Rotate binary tree node with right child.
     * For AVL trees, this is a single rotation for case 4.
     * Update heights, then set new root.
     */
    void rotateWithRightChild(AvlNode *&k1);
    /**
     * Double rotate binary tree node: first left child.
     * with its right child; then node k3 with new left child.
     * For AVL trees, this is a double rotation for case 2.
     * Update heights, then set new root.
     */
    void doubleWithLeftChild(AvlNode *&k3);
    /**
     * Double rotate binary tree node: first right child.
     * with its left child; then node k1 with new right child.
     * For AVL trees, this is a double rotation for case 3.
     * Update heights, then set new root.
     */
    void doubleWithRightChild(AvlNode *&k1);
};
/**
 * @brief A splaytree.
 * @tparam Comparable
 */
template <typename Comparable>
class SplayTree : public BstTree<Comparable>
{
protected:
    /**
     * @brief Node for splay tree.
     */
    struct SplayNode : BstTree<Comparable>::BstNode
    {
        SplayNode(const Comparable &theElement, SplayNode *lt, SplayNode *rt);
        SplayNode(Comparable &&theElement, SplayNode *lt, SplayNode *rt);
    };

private:
    SplayNode *root = nullptr;
    SplayNode *nullNode = nullptr;

public:
    virtual ~SplayTree();
    /**
     * Insert x into the tree; duplicates are ignored.
     */
    virtual void insert(const Comparable &x);
    virtual void insert(Comparable &&x);
    /**
     * Remove x from the tree. Nothing is done if x is not found.
     */
    virtual void remove(const Comparable &x);
    virtual void remove(Comparable &&x);

private:
    void rotateWithLeftChild(SplayNode *&k2);
    void rotateWithRightChild(SplayNode *&k1);
    /**
     * Internal method to perform a top-down splay.
     * The last accessed node becomes the new root.
     * This method may be overridden to use a different
     * splaying algorithm, however, the splay tree code
     * depends on the accessed item going to the root.
     * x is the target item to splay around.
     * t is the root of the subtree to splay.
     */
    void splay(const Comparable &x, SplayNode *&t);
};